class GameGraph():
    """画面信息"""
    def __init__(self, snake, food, scale_dict):
        self.snake = snake
        self.food = food
        self.scale_dict = scale_dict

    def set_food(self, food):
        """更新食物信息"""
        self.food = food


def viable(snake, origin):
    # 记录可走到的位置
    viable_positions = []

    # 初始位置
    snake_head = origin

    # 向右
    if snake_head[0] + 10 <= 180 and ((snake_head[0] + 10, snake_head[1]) not in snake):
        viable_positions.append((snake_head[0] + 10, snake_head[1]))

    # 向左
    if snake_head[0] - 10 >= -200 and ((snake_head[0] - 10, snake_head[1]) not in snake):
        viable_positions.append((snake_head[0] - 10, snake_head[1]))

    # 向上
    if snake_head[1] + 10 <= 190 and ((snake_head[0], snake_head[1] + 10) not in snake):
        viable_positions.append((snake_head[0], snake_head[1] + 10))

    # 向下
    if snake_head[1] - 10 >= -190 and ((snake_head[0], snake_head[1] - 10) not in snake):
        viable_positions.append((snake_head[0], snake_head[1] - 10))

    return viable_positions

# 我们用元组表示二维坐标，但元组不能作为字典的键，因此需要用 int 数据表示坐标
def new_xy(position):
    # return position[0]*15 + position[1]
    return position

def find_shortest_food_path(snake, food):
    """寻找食物的最短路径"""
    # 蛇头位置
    snake_head = snake[-1]

    # 是否找到食物
    food_flag = 0

    # 存储找到食物的最短路径
    food_path = [food]

    # 是否找到蛇尾
    tail_flag = 0

    ### 寻找食物
    # 搜索栈 -- 用于广度优先搜索
    search_stack = [snake_head]

    # 记录各个位置的先后关系 -- {当前位置：上一位置}
    position_relation = {new_xy(snake_head): -1}

    while True:
        # 获取当前蛇头下一步可走的位置
        origin = search_stack.pop(0)
        viable_positions = viable(snake, origin)

        # 如果找到食物
        if origin[0] == food[0] and origin[1] == food[1]:
            food_flag = 1
            break

        # 遍历下一步的可能位置
        for i in viable_positions:
            # 如果该位置未被搜索过
            if position_relation.get(new_xy(i)) == None:
                # 更新搜索栈
                search_stack.append(i)
                # 更新位置关系
                position_relation[new_xy(i)] = origin

        # 如果找不到食物
        if len(search_stack) == 0:
            break

    # 记录找到食物的最短路径
    if food_flag == 1:
        while True:
            p = position_relation[new_xy(food_path[-1])]
            if p == -1:
                break
            else:
                food_path.append(p)

        food_path.reverse()

    return food_flag, food_path

def find_shortest_tail_path(snake):
    """寻找蛇尾的最短路径"""
    tail_flag, tail_path = find_shortest_food_path(snake[1:], snake[0])
    return tail_flag, tail_path

def find_longest_path(snake):
    """寻找蛇尾的最长路径"""
    snake_head = snake[0]

    # 记录最长路径的长度
    longest = -1
    next_position = 0

    # 搜索栈 -- 用于广度优先搜索
    search_stack = [snake_head]

    # 记录各个位置的先后关系 -- {当前位置：上一位置}
    position_relation = {new_xy(snake_head): -1}

    # 获取当前蛇头下一步可走的位置
    origin = search_stack.pop(0)
    viable_positions = viable(snake, origin)

    for i in viable_positions:
        snake_temp = snake.copy()
        snake_temp.append(i)
        _, tail_path = find_shortest_tail_path(snake_temp)

        if len(tail_path) > longest:
            next_position = i
            longest = len(tail_path)

    return next_position


def exploation(snake_temp, food):
    """虚拟蛇探路，看看吃到食物后，还能不能找到蛇尾"""
    food_flag, food_path = find_shortest_food_path(snake_temp, food)
    food_path.pop(0)

    while True:
        p = food_path.pop(0)
        snake_temp.append(p)

        if p[0] == food[0] and p[1] == food[1]:
            break

        else:
            snake_temp.pop(0)

    tail_flag, _ = find_shortest_tail_path(snake_temp)
    return tail_flag

def pathfinding(game_graph):
    """寻找路径"""
    # 蛇身信息
    snake = game_graph.snake

    # 蛇头坐标
    snake_head = game_graph.snake[-1]

    # 蛇尾坐标
    snake_tail = game_graph.snake[0]

    # 食物坐标
    food = game_graph.food

    # 找到最短食物路径
    food_flag, food_path = find_shortest_food_path(snake, food)

    # 如果当前存在 最短食物路径
    if food_flag == 1:
        # 虚拟蛇探路，看看吃到食物后，还能不能找到蛇尾
        snake_temp = snake.copy()
        tail_flag = exploation(snake_temp, food)

        if tail_flag == 1:
            # 还能找到蛇尾，则这条路径可行
            print("路径安全，可以进食")
            print("食物路径：",food_path)
            # 更新蛇的位置
            food_path.pop(0)
            p = food_path.pop(0)
            snake.append(p)
            snake.pop(0)

        else:
            # 吃到食物过后，找不到蛇尾 -- 找到到达蛇尾的最长路径，向此方向走一步
            print('路径不安全，找蛇尾')
            next_position = find_longest_path(snake)
            snake.append(next_position)
            snake.pop(0)

    else:
        # 如果当前不存在,最短食物路径
        # 找到到达蛇尾的最长路径，向此方向走一步
        print('路径不安全，找蛇尾')
        next_position = find_longest_path(snake)
        snake.append(next_position)
        snake.pop(0)

    # 返回方向
    return snake[-1][0] - snake_head[0], snake[-1][1] - snake_head[1]








